
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Kademlia}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Peer ID}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
原始论文中并未明确指定ID的生成规则，示例中使用的是$sha1(PubKey)$。


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Distance}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
如Figure \ref{fig:distance}所示，更多相同的前导位数，意味着更近的\emph{节点距离}。


\begin{figure}[htbp!]
    \centering
    \includegraphics[scale=0.32]{distance.jpg}
    \caption{distance}
    \label{fig:distance}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{DHT}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
如Figure  \ref{fig:dht} 所示，一个Kademlia节点包含三个关键要素：
ID、路由表\footnote{对应图中的Routing Table}、
文件影射表\footnote{对应图中的DHT Segment}，
其中ID用于标识节点的唯一身份，路由表用于存储已知的有效节点信息，文件影射表用于索引本机存储的文件。

\begin{figure}[htbp!]
    \centering
    \includegraphics[scale=0.31]{dht.jpg}
    \caption{DHT}
    \label{fig:dht}
\end{figure}

\subsection{k-bucket}
如Figure \ref{fig:k-bucket}所示，路由信息是按照每个外部节点与本节点的距离远近，按照一定的规则分组存储的。
这个分组结构称为k-bucket，意指将目标信息分别存放到不同的桶中。\par
如下，假设某外部节点与本节点的距离为$distance$，则其应该被存储在编号为$bucketID$的桶中，
能够存储到这个桶中的外部节点与本节点的距离取值范围为$distanceRange$，这个桶的最大容量为$capacity$。
\begin{align*}
	&bucketID=floor(log_2^{distance})\\
	&capacity=[0,k]\emph{，其中k为常数}\\
	&distanceRange=[2^{ID},2^{ID+1})
\end{align*}

\begin{figure}[htbp!]
    \centering
    \includegraphics[scale=0.31]{k_bucket.jpg}
    \caption{k-bucket}
    \label{fig:k-bucket}
\end{figure}

\subsection{routing table}
\begin{center}
    \includegraphics[scale=0.26]{routing_table.jpg}
\end{center}

\subsection{bucket split}
\begin{center}
    \includegraphics[scale=0.31]{bucket_split.jpg}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Bootstrap}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
需要从事先定义好的公共节点获取初始的DHT。


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Discovery}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
    \includegraphics[scale=0.31]{discovery.jpg}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Summary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Kademlia采用XOR计算距离，使其在路由查找时拥有$\log_2^n$的算法复杂度，相对Chord等更早的协议更加高效；
同时，其\emph{旧者优先}的节点替换原则，对防范DDOS攻击具有一定的作用。\par
但其缺点也是显而易见的：
\begin{itemize}
    \item 在网络安全方面的考虑不足，如节点ID可任意生成、路由查找时允许存在重复的路径等
    \item 完全依据随机生成的节点ID计算彼此之间的距离，而没有考虑实际地理位置造成的影响，如网络延迟等
    \item \emph{旧者优先}原则存在缺陷，如某个节点启动时即被很多恶意节点包围等
\end{itemize}
